The present invention relates in general to digital multipliers and more specifically to improving the speed at which partial products are summed to form the final product of the multiplication.
Binary multiplication is an important function in many digital signal processing applications. Some applications further require accumulation of a product with the results of previous operations (e.g. forming a sum of products). A versatile multiplier circuit must have the capability to perform these functions in either two's complement or unsigned magnitude notation.
Many schemes are known in the art for reducing the time required to perform a binary multiplication. For example, many different encoding methods have been devised which reduce the number of partial products which must be added up to form the final product. The modified Booth algorithm is one of these which is often used in integrated circuit digital multipliers.
Attempts have also been made to speed up the summation of the partial products. In U.S. Pat. No. 4,545,028, issued to Ware, the adder array is divided into blocks so that different blocks can perform different parts of the addition in parallel, even though all of the addition within each block is done in ripple fashion. Furthermore, the first block can only contain four partial products and the remaining blocks must match an arithmetic progression so that carries from one block appear when needed by the next block.
Summation can also be speeded up through use of a carry look-ahead adder. The propagation of carries through a sequential series of adder stages in ripple fashion requires a greater period of time the greater the number of bits in the addends. In a carry look-ahead adder, logic circuitry provides concurrent carry propagation rather than sequential. However, the bit size of a carry look-ahead adder is limited because the circuit complexity, gate count and chip area rapidly increase as bit size increases.
Accordingly, it is a principal object of the present invention to provide a circuit and method for fast, parallel summation of partial products with minimum added complexity and space in an integrated circuit.
It is another object to provide an improved, high-speed adder architecture adapted to provide accumulation and adapted to handle either signed or unsigned notation.
It is yet another object of the invention to provide high-speed binary multiplication with a parallel adder architecture which can be implemented with standard IC technology.